# -*- coding: utf-8 -*-            
# @Time : 2022/10/29 16:37
# @Author  : lining
# @FileName: demo5.py
"""
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
想法1：在入栈的时候取出最小值，然后另外保存起来，但是在pop的时候如果pop的正好是最小值，这时候就没有最小值-----不行
想法2；既然我们已经在取最小值的时候已经拿过前n个的最小值，我们就把这些历史记录保存起来,放到另一个栈
没插入一个数都要在最小值栈放入一个值，这样有重复数据就不会出错

"""
class MinStack(object):

    def __init__(self):
        # 栈1，存放数据
        self.stack = []
        # 栈2，存放历史最小值
        self.stack_min = []


    def push(self, val):
        """
        将元素推入栈
        1.数据栈推入
        2.将最小值推入
        :type val: int
        :rtype: None
        """
        self.stack.append(val)
        if not self.stack_min:
            self.stack_min.append(val)
        else:
            self.stack_min.append(min(self.getMin(), val))


    def pop(self):
        """
        1.原数据栈要pop
        2.最小值栈要做比较
        :rtype: None
        """
        self.stack.pop()
        self.stack_min.pop()


    def top(self):
        """
        获取顶部数据
        :rtype: int
        """
        return self.stack[-1]


    def getMin(self):
        """
        :rtype: int
        """
        # print(self.stack_min[-1])
        return self.stack_min[-1]


a = MinStack()
for i in [9,8,7,6,5,4,3,2,1,0]:
    a.push(i)
print(a.getMin())
a.pop()
print(a.getMin())
a.pop()
print(a.getMin())
